home *** CD-ROM | disk | FTP | other *** search
/ CD ROM Paradise Collection 4 / CD ROM Paradise Collection 4 1995 Nov.iso / program / swagn_r.zip / POINTERS.SWG / 0029_Linked lists in Expanded Memory.pas < prev    next >
Pascal/Delphi Source File  |  1995-03-03  |  14KB  |  369 lines
  1. {
  2.        PROTOTYPE PROCEDURES FOR CREATING AND ACCESSING SORTED
  3.                  LINKED LISTS IN EXPANDED MEMORY
  4.  
  5.                   GARRY J. VASS [72307,3311]
  6.  
  7. The procedures and functions given below present a prototype
  8. method for creating and accesing linked lists in expanded memory.
  9. Although pointer variables are used in a way that appears to
  10. conform to the TPascal pointer syntax, there are several major
  11. differences:
  12.  
  13.             -  there are none of the standard NEW, GETMEM,
  14.                MARK, RELEASE, DISPOSE, FREEMEM, and MAXAVAIL
  15.                calls made.  These are bound to the program's
  16.                physical location in memory, and have no
  17.                effect in expanded memory.  Attempting to
  18.                use these here, or to implement standard
  19.                linked procedures by altering the HeapPtr
  20.                standard variable is dangerous and highly
  21.                discouraged.
  22.             -  pointer variables are set and queried by
  23.                a simulation of TPascal's internal procedures
  24.                that is specially customized to the EMS
  25.                page frame segment.
  26.             -  the MEMAVAIL function is useless here.  These
  27.                procedures will support a list of up to 64K.
  28.  
  29. The general pseudo-code for creating a linked list in expanded
  30. memory is:
  31.  
  32.       1.  Get a handle and allocate memory from the EMM.
  33.       2.  Get the page frame segment for the handle to
  34.           mark the physical beginning of the list in
  35.           expanded memory.
  36.       3.  Initialize the root pointer to the page frame
  37.           segment.
  38.       4.  For each new record (or list member):
  39.  
  40.           a.  Calculate a new physical location for the
  41.               record using a simulated normalization
  42.               procedure.
  43.           b.  Set the appropriate values to the
  44.               pointers using a simulated pointer
  45.               assignment procedure.
  46.           c.  Assure that the last logical record
  47.               contains a pointer value of NIL.
  48.  
  49. Accessing the list is basically the same as the standard algorithms.
  50.  
  51. The procedures here assume that each list record (or member) is composed
  52. of three elements:
  53.  
  54.         -  a pointer to the next logical record.  If the member is the
  55.            last logical record, this pointer is NIL.
  56.         -  an index, or logical sort key.  This value determines the
  57.            logical position of the record in the list.  These routines
  58.            and the demo use an integer type for index.  The index,
  59.            however, can be of any type where ordinal comparisons
  60.            can be made, including pointers.
  61.         -  an area for the actual data in each record.  These routines
  62.            and the demo use a string of length 255, but this area can
  63.            be of any type, including pointers to other lists.
  64.  
  65. Please note that these routines are exploratory and prototype.  In no way
  66. are they intended to be definitive, accurate, efficient, or exemplary.
  67.  
  68. Areas for further analysis are:
  69.  
  70.       1.  A reliable analog to the MEMAVAIL function.
  71.       2.  Creating linked lists that cross handle boundaries.
  72.       3.  Creating linked lists that begin in heapspace and
  73.           extend to expanded memory.
  74.       4.  A reliable method for assigning the standard
  75.           variable, HeapPtr, to the base page.
  76.  
  77. Please let me know of your progress in these areas, or improvements
  78. to the routines below via the BORLAND SIG [72307,3311] or my PASCAL/
  79. PROLOG SIG at the POLICE STATION BBS (201-963-3115).
  80.  
  81. }
  82. PROGRAM LINKED_LISTS;
  83. Uses dos,crt;
  84. CONST
  85.      ALLOCATE_MEMORY =   $43;
  86.      EMS_SERVICES    =   $67;
  87.      FOREVER:BOOLEAN = FALSE;
  88.      GET_PAGE_FRAME  =   $41;
  89.      LOGICAL_PAGES   =     5;
  90.      MAP_MEMORY      =   $44;
  91.      RELEASE_HANDLE  =   $45;
  92. TYPE
  93.     ANYSTRING = STRING[255];
  94.     LISTPTR   = ^LISTREC;
  95.     LISTREC   = RECORD
  96.                       NEXT_POINTER : LISTPTR;
  97.                       INDEX_PART   : INTEGER;
  98.                       DATA_PART    : ANYSTRING;
  99.                 END;
  100. VAR
  101.    ANYINTEGER : INTEGER;
  102.    ANYSTR     : ANYSTRING;
  103.    HANDLE     : INTEGER;    { HANDLE ASSIGNED BY EMM }
  104.    LIST       : LISTREC;
  105.    NEWOFFSET  : INTEGER;    { PHYSICAL OFFSET OF RECORD }
  106.    NEWSEGMENT : INTEGER;    { PHYSICAL SEGMENT OF RECORD }
  107.    REGS1      : Registers;
  108.    ROOT       : LISTPTR;    { POINTER TO LIST ROOT }
  109.    SEGMENT    : INTEGER;    { PAGE FRAME SEGMENT }
  110.  
  111. {--------------------- GENERAL SUPPORT ROUTINES  ----------------------}
  112. FUNCTION HEXBYTE(N:INTEGER):ANYSTRING;
  113. CONST H:ANYSTRING='0123456789ABCDEF';
  114. BEGIN
  115.      HEXBYTE:=H[((LO(N)DIV 16)MOD 16)+1]+H[(LO(N) MOD 16)+1];
  116. END;
  117.  
  118. FUNCTION HEXWORD(N:INTEGER):ANYSTRING;
  119. BEGIN
  120.      HEXWORD:= HEXBYTE(HI(N))+HEXBYTE(LO(N));
  121. END;
  122.  
  123. FUNCTION CARDINAL(I:INTEGER):REAL;
  124. BEGIN
  125.      CARDINAL:=256.0*HI(I)+LO(I);
  126. END;
  127.  
  128. PROCEDURE  PAUSE;
  129. VAR CH:CHAR;
  130. BEGIN
  131.      WRITELN;WRITELN('-- PAUSING FOR KEYBOARD INPUT...');
  132.      READ(CH);
  133.      WRITELN;
  134. END;
  135.  
  136. PROCEDURE DIE(M:ANYSTRING);
  137. BEGIN
  138.      WRITELN('ERROR IN: ',M);
  139.      WRITELN('HALTING HERE, SUGGEST REBOOT');
  140.      HALT;
  141. END;
  142. FUNCTION EXIST(FILENAME:ANYSTRING):BOOLEAN;VAR FILVAR:FILE;BEGIN ASSIGN(FILVAR,FILENAME);{$I-}
  143. RESET(FILVAR);{$I+}EXIST := (IORESULT = 0);END;
  144. {--------------------- END OF GENERAL SUPPORT ROUTINES  ----------------}
  145.  
  146. {----------------------  EMS SUPPORT ROUTINES  -------------------------}
  147.  
  148. FUNCTION EMS_INSTALLED:BOOLEAN;         { RETURNS TRUE IF EMS IS INSTALLED }
  149. BEGIN                                   { ASSURED DEVICE NAME OF EMMXXXX0  }
  150.      EMS_INSTALLED := EXIST('EMMXXXX0');{ BY LOTUS/INTEL/MS STANDARDS      }
  151. END;
  152.  
  153. FUNCTION NEWHANDLE(NUMBER_OF_LOGICAL_PAGES_NEEDED:INTEGER):INTEGER;
  154. BEGIN
  155.      REGS1.AH := ALLOCATE_MEMORY;
  156.      REGS1.BX := NUMBER_OF_LOGICAL_PAGES_NEEDED;
  157.      INTR(EMS_SERVICES, REGS1);
  158.      IF REGS1.AH <> 0 THEN DIE('ALLOCATE MEMORY');
  159.      NEWHANDLE := REGS1.DX;
  160. END;
  161.  
  162. PROCEDURE KILL_HANDLE(HANDLE_TO_KILL:INTEGER);  { RELEASES EMS HANDLE.    }
  163. BEGIN                                           { THIS MUST BE DONE IF    }
  164.      REPEAT                                     { OTHER APPLICATIONS ARE  }
  165.           WRITELN('RELEASING EMS HANDLE');      { TO USE THE EM ARES.  DUE}
  166.           REGS1.AH := RELEASE_HANDLE;            { TO CONCURRENT PROCESSES,}
  167.           REGS1.DX := HANDLE_TO_KILL;            { SEVERAL TRIES MAY BE    }
  168.           INTR(EMS_SERVICES, REGS1);             { NECESSARY.              }
  169.      UNTIL REGS1.AH = 0;
  170.      WRITELN('HANDLE RELEASED');
  171. END;
  172.  
  173. FUNCTION PAGE_FRAME_SEGMENT:INTEGER;         { RETURNS PFS }
  174. BEGIN
  175.      REGS1.AH := GET_PAGE_FRAME;
  176.      INTR(EMS_SERVICES, REGS1);
  177.      IF REGS1.AH <> 0 THEN DIE('GETTING PFS');
  178.      PAGE_FRAME_SEGMENT := REGS1.BX;
  179. END;
  180.  
  181. PROCEDURE MAP_MEM(HANDLE_TO_MAP:INTEGER);  {MAPS HANDLE TO PHYSICAL}
  182. CONST PHYSICAL_PAGE = 0;                 {PAGES.}
  183. BEGIN
  184.      REGS1.AH := MAP_MEMORY;
  185.      REGS1.AL := PHYSICAL_PAGE;
  186.      REGS1.BX := PHYSICAL_PAGE;
  187.      REGS1.DX := HANDLE_TO_MAP;
  188.      INTR(EMS_SERVICES, REGS1);
  189.      IF REGS1.AH <> 0 THEN DIE('MAPPING MEMORY');
  190. END;
  191.  
  192. PROCEDURE GET_EMS_MEMORY(NUMBER_OF_16K_LOGICAL_PAGES:INTEGER);
  193. VAR TH:INTEGER;                     { REQUESTS EM FROM EMM IN 16K INCREMENTS }
  194. BEGIN
  195.      HANDLE :=  NEWHANDLE(NUMBER_OF_16K_LOGICAL_PAGES);
  196.      SEGMENT := PAGE_FRAME_SEGMENT;
  197.      MAP_MEM(HANDLE);
  198. END;
  199. {----------------- END OF EMS SUPPORT ROUTINES  -----------------------}
  200.  
  201. {----------------- CUSTOMIZED LINKED LIST SUPPORT ---------------------}
  202. FUNCTION ABSOLUTE_ADDRESS(S, O:INTEGER):REAL;   { RETURNS THE REAL }
  203. BEGIN                                           { ABSOLUTE ADDRESS }
  204.      ABSOLUTE_ADDRESS :=  (CARDINAL(S) * $10)   { FOR SEGMENT "S"  }
  205.                          + CARDINAL(O);         { AND OFFSET "O".  }
  206. END;
  207.  
  208. PROCEDURE NORMALIZE(VAR S, O:INTEGER); { SIMULATION OF TURBO'S INTERNAL }
  209. VAR                                    { NORMALIZATION ROUTINES FOR     }
  210.    NEW_SEGMENT: INTEGER;               { POINTER VARIABLES.             }
  211.    NEW_OFFSET : INTEGER;               { NORMALIZES SEGMENT "S" AND     }
  212. BEGIN                                  { OFFSET "O" INTO LEGITAMATE     }
  213.      NEW_SEGMENT := S;                 { POINTER VALUES.                }
  214.      NEW_OFFSET  := O;
  215.      REPEAT
  216.            CASE NEW_OFFSET OF
  217.               $00..$0E   : NEW_OFFSET := SUCC(NEW_OFFSET);
  218.               $0F..$FF   : BEGIN
  219.                                NEW_OFFSET := 0;
  220.                                NEW_SEGMENT := SUCC(NEW_SEGMENT);
  221.                            END;
  222.            END;
  223.      UNTIL  (ABSOLUTE_ADDRESS(NEW_SEGMENT, NEW_OFFSET) >
  224.              ABSOLUTE_ADDRESS(S, O) + SIZEOF(LIST));
  225.      S := NEW_SEGMENT;
  226.      O := NEW_OFFSET;
  227. END;
  228.  
  229. FUNCTION VALUEOF(P:LISTPTR):ANYSTRING;  { RETURNS A STRING IN   }
  230.                                         { SEGMENT:OFFSET FORMAT }
  231.                                         { WHICH CONTAINS VALUE  }
  232. BEGIN                                   { OF A POINTER VARIABLE }
  233.      VALUEOF := HEXBYTE(MEM[SEG(P):OFS(P) + 3]) +
  234.                 HEXBYTE(MEM[SEG(P):OFS(P) + 2]) +':'+
  235.                 HEXBYTE(MEM[SEG(P):OFS(P) + 1]) +
  236.                 HEXBYTE(MEM[SEG(P):OFS(P) + 0]);
  237. END;
  238.  
  239. PROCEDURE SNAP(P:LISTPTR);                   { FOR THE RECORD BEING         }
  240. BEGIN                                        { POINTED TO BY "P", THIS      }
  241.      WRITELN(VALUEOF(P):10,                  { PRINTS THE SEGMENT/OFFSET    }
  242.              VALUEOF(P^.NEXT_POINTER):20,    { LOCATION, THE SEGMENT/       }
  243.              P^.INDEX_PART:5,                { OFFSET OF THE RECORD PONTER, }
  244.              '     ',P^.DATA_PART);          { RECORD INDEX, AND DATA.      }
  245. END;
  246.  
  247. PROCEDURE PROCESS_LIST;               { GET AND PRINT MEMBERS OF A LIST }
  248. VAR M1:LISTPTR;                       { SORTED IN INDEX ORDER.          }
  249. BEGIN
  250.      PAUSE;
  251.      M1 := ROOT;
  252.      WRITELN;
  253.      WRITELN('---------------- LINKED LIST ---------------------------------');
  254.      WRITELN('MEMBER LOCATION           MEMBER CONTENTS');
  255.      WRITELN('IN MEMORY             POINTER    INDEX  DATA   ');
  256.      WRITELN('---------------       -----------------------------------------');
  257.      WRITELN;
  258.      REPEAT
  259.            SNAP(M1);
  260.            M1 := M1^.NEXT_POINTER;
  261.      UNTIL M1 = NIL;
  262.      WRITELN('------------ END OF LIST----------');
  263. END;
  264.  
  265. PROCEDURE LOAD_MEMBER_HIGH (IND:INTEGER; DAT:ANYSTRING);
  266. VAR M1:LISTPTR;
  267.      P:LISTPTR;                  { INSERTS A RECORD AT THE HIGH }
  268. BEGIN                            { END OF THE LIST.             }
  269.      M1 := ROOT;
  270.      REPEAT
  271.            IF M1^.NEXT_POINTER <> NIL THEN M1 := M1^.NEXT_POINTER;
  272.      UNTIL M1^.NEXT_POINTER = NIL;
  273.      NORMALIZE(NEWSEGMENT, NEWOFFSET);
  274.      M1^.NEXT_POINTER := PTR(NEWSEGMENT, NEWOFFSET);
  275.      P := M1^.NEXT_POINTER;
  276.      P^.INDEX_PART := IND;
  277.      P^.DATA_PART := DAT;
  278.      P^.NEXT_POINTER := NIL;
  279. END;
  280.  
  281. PROCEDURE LOAD_MEMBER_MIDDLE (IND:INTEGER; DAT:ANYSTRING);
  282. VAR M1:LISTPTR;
  283.     M2:LISTPTR;
  284.     P :LISTPTR;
  285.     T :LISTPTR;
  286. BEGIN                         { INSERTS A MEMBER INTO THE MIDDLE }
  287.      M1 := ROOT;              { OF A LIST.                       }
  288.      REPEAT
  289.            M2 := M1;
  290.            IF M1^.NEXT_POINTER <> NIL THEN M1 := M1^.NEXT_POINTER;
  291.      UNTIL (M1^.NEXT_POINTER = NIL) OR (M1^.INDEX_PART >= IND);
  292.      IF (M1^.NEXT_POINTER = NIL) AND
  293.         (M1^.INDEX_PART <   IND) THEN
  294.         BEGIN
  295.              LOAD_MEMBER_HIGH (IND, DAT);
  296.              EXIT;
  297.         END;
  298.      T := M2^.NEXT_POINTER;
  299.      NORMALIZE(NEWSEGMENT, NEWOFFSET);
  300.      M2^.NEXT_POINTER := PTR(NEWSEGMENT, NEWOFFSET);
  301.      P := M2^.NEXT_POINTER;
  302.      P^.INDEX_PART := IND;
  303.      P^.DATA_PART := DAT;
  304.      P^.NEXT_POINTER := T;
  305. END;
  306.  
  307. PROCEDURE LOAD_MEMBER (IND:INTEGER; DAT:ANYSTRING);
  308. VAR  M1:LISTPTR;
  309. BEGIN
  310.      WRITELN('ADDING:  ',DAT,' WITH AGE OF ',IND);
  311.      WRITELN('TURBO`S HEAP POINTER:  ',VALUEOF(HEAPPTR),
  312.              ', MEMAVAIL = ',MEMAVAIL * 16.0:8:0);
  313.      WRITELN;
  314.      PAUSE;
  315.      WRITELN('... SEARCHING FOR ADD POINT ...');
  316.      IF ROOT^.INDEX_PART <= IND THEN             { ENTRY POINT ROUTINE FOR }
  317.         BEGIN                                    { ADDING NEW LIST MEMBERS }
  318.              LOAD_MEMBER_MIDDLE(IND, DAT);       { ACTS ONLY IF NEW MEMBER }
  319.              EXIT;                               { SHOULD REPLACE CURRENT  }
  320.         END;                                     { ROOT.                   }
  321.      M1 := ROOT;
  322.      NORMALIZE(NEWSEGMENT, NEWOFFSET);
  323.      ROOT := PTR(NEWSEGMENT, NEWOFFSET);
  324.      ROOT^.INDEX_PART   := IND;
  325.      ROOT^.DATA_PART    := DAT;
  326.      ROOT^.NEXT_POINTER := M1;
  327. END;
  328.  
  329. PROCEDURE INITIALIZE_ROOT_ENTRY(IND:INTEGER; DAT:ANYSTRING);
  330. BEGIN
  331.      ROOT := PTR(NEWSEGMENT, NEWOFFSET);       { INITIALIZES A LIST AND }
  332.      ROOT^.INDEX_PART   := IND;                { ADDS FIRST MEMBER AS   }
  333.      ROOT^.DATA_PART    := DAT;                { "ROOT".                }
  334.      ROOT^.NEXT_POINTER := NIL;
  335. END;
  336.  
  337. BEGIN
  338.      TEXTCOLOR(15);
  339.      IF NOT EMS_INSTALLED THEN DIE('LOCATING EMS DRIVER');
  340.      CLRSCR;
  341.      WRITELN('DEMO OF LINKED LIST IN EXPANDED MEMORY...');
  342.      WRITELN('SETTING UP EMS PARAMETERS...');
  343.      GET_EMS_MEMORY(LOGICAL_PAGES);
  344.      WRITELN;
  345.      WRITELN('ASSIGNED HANDLE:  ',HANDLE);
  346.      NEWSEGMENT := SEGMENT;
  347.      NEWOFFSET  := 0;
  348.      WRITELN('EMS PARAMETERS SET.  BASE PAGE IS:  ',HEXWORD(SEGMENT));
  349.      WRITELN;
  350.      WRITELN('TURBO`S HEAP POINTER IS ',VALUEOF(HEAPPTR));
  351.      WRITELN('READY TO ADD RECORDS...');
  352.      PAUSE;
  353.  
  354. { Demo:  Create a linked list of names and ages with age as the index/sort
  355.   key.  Use random numbers for the ages so as to get a different sequence
  356.   each time the demo is run.}
  357.  
  358.      INITIALIZE_ROOT_ENTRY(RANDOM(10) + 20, 'Anne Baxter (original root)');
  359.      LOAD_MEMBER(RANDOM(10) + 20,  'Rosie Mallory  ');
  360.      LOAD_MEMBER(RANDOM(10) + 20,  'Sue Perkins    ');
  361.      LOAD_MEMBER(RANDOM(10) + 20,  'Betty Williams ');
  362.      LOAD_MEMBER(RANDOM(10) + 20,  'Marge Holly    ');
  363.      LOAD_MEMBER(RANDOM(10) + 20,  'Lisa Taylor    ');
  364.      LOAD_MEMBER(RANDOM(10) + 20,  'Carmen Abigail ');
  365.      LOAD_MEMBER(RANDOM(10) + 20,  'Rhonda Perlman ');
  366.      PROCESS_LIST;
  367.      KILL_HANDLE(HANDLE);
  368. END.
  369.